Your browser doesn't support the features required by impress.js, so you are presented with a simplified version of this presentation.

For the best experience please use the latest Chrome, Safari or Firefox browser.

\[ \newcommand{\IR}{\mathbb{R}} \newcommand{\IRnn}{\IR_{\geq 0}} \newcommand{\coloneqq}{:=} \newcommand{\eqqcolon}{=:} \newcommand{\sMid}{\,|\,} \newcommand{\SMid}{\middle|} \newcommand{\transp}{^\top} \]

§2 Computation of Mixed Nash Equilibria

Throughout this chapter: Only finite 2-player games $G=([2],S,u)$

Notation: $S_1 = M \coloneqq \set{1,\dots,m}$,   $S_2 = N = \set{m+1,\dots,m+n}$,   $A,B \in \IR^{M\times N}$ utility matrices of player 1/2

§2.1 Full Support Enumeration

Obs. 1.8: $x^* \in \Delta$ is MNE $\iff x^* \in B(x^*) \coloneqq \prod_i B_i(x^*_{-i})$ where $B_i(x^*_{-i}) \coloneqq \set{x_i \in \Delta(S_i) \sMid x_i \text{ best resp. to } x^*_{-i}}$

Thm. 2.2 (Best-Response-Condition (BRC)): $(x,y) \in \Delta$ mixed strategy profile. Then:
  • $x$ best response to $y$ $\iff \bigl(\forall i \in M: x_i \gt 0 \implies (Ay)_i = \max\set{(Ay)_k \sMid k \in M} \class{tempstep a}{\data{tempstep-from=11}{\eqqcolon u}}\bigr)$
  • $y$ best response to $x$ $\iff \bigl(\forall j \in N: y_j \gt 0 \implies (x\!\transp\! B)_j = \max\set{(x\!\transp\! B)_\ell \sMid \ell \in N} \class{tempstep a}{\data{tempstep-from=11}{\eqqcolon v}}\bigr)$
Alg. 2.1: Full Support Enumeration
Input: Finite 2-player game $G=(N,S,u)$
Output: A mixed NE of $G$
  1. For each $I \subseteq M, J \subseteq N$ Do
  2. mmSolve the system of linear inequalities: \begin{align*} \sum_{i \in I} x_i B_{ij} = v \quad \forall j \in J \qquad & \text{and} \qquad \sum_{i \in I} x_i = 1 \\ \sum_{j \in J} A_{ij} y_j = u \quad \forall i \in I \qquad & \text{and} \qquad \sum_{j \in J} y_j = 1 \\ \sum_{i \in I} x_i B_{ij} \leq v \quad \forall j \in N \setminus J \qquad &\text{and} \qquad x_i \geq 0 \quad \forall i \in I \\ \sum_{j \in J} A_{ij} y_j \leq u \quad \forall i \in M \setminus I \qquad & \text{and} \qquad y_j \geq 0 \quad \forall j \in J \end{align*}
  3. mmIf $\exists$ solution $(x,y)$ Then
  4. mmmmReturn $(x,y)$ (extended with zeros)
Example 2.3: Determine all MNE in the following game:
$4$$5$
$1$$(3\class{clickedVisC}{^*},3\class{clickedVisR}{^*})$$(3\phantom{^*},2\phantom{^*})$
$2$$(2\phantom{^*},2\phantom{^*})$$(5\phantom{^*},6\class{clickedVisR}{^*})$
$3$$(0\phantom{^*},3\class{clickedVisR}{^*})$$(6\class{clickedVisC}{^*},1\phantom{^*})$
Thm. 2.2 (Best-Response-Condition (BRC)): $(x,y) \in \Delta$ mixed strategy profile. Then:
  • $x$ best response to $y$ $\iff \!\bigl(\forall i \in M: x_i \gt 0 \implies (Ay)_i = \max\set{(Ay)_k \sMid k \in M} \eqqcolon u\bigr)\!$
  • $y$ best response to $x$ $\iff \!\bigl(\forall j \in N: y_j \gt 0 \implies (x\!\transp\! B)_j = \max\set{(x\!\transp\! B)_\ell \sMid \ell \in N} \eqqcolon v\bigr)\!$
Best-Response-Polyhedra: \begin{align*} \bar{P_1} &\coloneqq \set{(x,v) \in \IR^M \times \IR \sMid \forall j \in N: (x\transp B)_j \leq v, \sum\nolimits_{i \in M}x_i = 1, \forall i \in M: x_i \geq 0} \\ \data{tempstep-classes=7-30:red}{\class{tempstep}{\bar{P_2}}} &\data{tempstep-classes=7-30:red}{\class{tempstep}{\,\coloneqq \set{(y,u) \in \IR^N \times \IR \sMid \forall i \in M: (A y)_i \leq u, \,\,\,\;\sum\nolimits_{j \in N}y_j = 1, \forall y \in N: y_j \geq 0}}} \end{align*}
$(x,v) \in \bar{P_1}$ has label $k \in M \cup N$ $:\iff k \in N \land (x\transp B)_k = v \,\,\,\;\lor\quad k \in M \land x_k = 0$
$(y,u) \in \bar{P_2}$ has label $k \in M \cup N$ $:\iff k \in M \land (A y)_k = u \quad\lor\quad k \in N \land y_k = 0$
Thm. 2.7: $(x,y) \in \Delta$ is MNE with utilities $u,v \in \IR \iff (x,v) \in \bar{P_1}, (y,u) \in \bar{P_2}$ have all labels.
Asmpt. 2.8: $A,B\transp$ non-negative and without zero columns
\begin{align*} P_1 &\coloneqq \set{x \in \IR^M \sMid \forall j \in N: (x\transp B)_j \leq 1, \phantom{\sum\nolimits_{i \in M}x_i = 1,} \forall i \in M: x_i \geq 0} \\ P_2 &\coloneqq \set{y \in \IR^N \sMid \forall i \in M: (A y)_i \leq 1, \,\,\,\;\phantom{\sum\nolimits_{j \in N}y_j = 1,} \forall y \in N: y_j \geq 0} \end{align*}
Lem. 2.9: $\bar{P_1} \to P_1 \setminus \{0\}, (x,v) \mapsto \tfrac{1}{v}x$,   $\bar{P_2} \to P_2 \setminus \{0\}, (y,u) \mapsto \tfrac{1}{u}y$ label-invariant bij's.
Thm. 2.7': $\displaystyle\Bigl(\frac{x}{\sum_i x},\frac{y}{\sum_j y_j}\Bigr) \in \Delta$ is MNE $\iff x \in P_1 \setminus \{0\}, y \in P_2 \setminus \{0\}$ have all labels.
Example 2.3:
$4$$5$
$1$$(\data{tempstep-classes=7-8:red}{\class{tempstep}{3}},3)$$(\data{tempstep-classes=7-8:red}{\class{tempstep}{3}},2)$
$2$$(\data{tempstep-classes=7-8:red}{\class{tempstep}{2}},2)$$(\data{tempstep-classes=7-8:red}{\class{tempstep}{5}},6)$
$3$$(\data{tempstep-classes=7-8:red}{\class{tempstep}{0}},3)$$(\data{tempstep-classes=7-8:red}{\class{tempstep}{6}},1)$
\Huge y_4 \Huge u \Huge 1 \Huge y_5 \Huge1 \Huge1 \Huge\Delta(S_2) \Huge\bar{P_2} \Huge\color{var(--x1color)}3 \Huge\color{var(--x1color)}3 \Huge\color{var(--x2color)}2 \Huge\color{var(--x2color)}5 \Huge\color{var(--x3color)}0 \Huge\color{var(--x3color)}6 \Huge P_2
\begin{align*} \phantom{0y_0 + \,}\data{tempstep-classes=24:x1hl}{\class{tempstep}{\data{tempstep-classes=8:red}{\class{tempstep}{3}}y_4 + \data{tempstep-classes=8:red}{\class{tempstep}{3}}y_5}} &\data{tempstep-classes=24:x1hl}{\class{tempstep}{\,\leq u}} \\ \data{tempstep-classes=25:x2hl}{\class{tempstep}{\data{tempstep-classes=8:red}{\class{tempstep}{2}}y_4 + \data{tempstep-classes=8:red}{\class{tempstep}{5}}y_5}} &\data{tempstep-classes=25:x2hl}{\class{tempstep}{\,\leq u}} \\ \data{tempstep-classes=26:x3hl}{\class{tempstep}{\data{tempstep-classes=8:red}{\class{tempstep}{0}}y_4 + \data{tempstep-classes=8:red}{\class{tempstep}{6}}y_5}} &\data{tempstep-classes=26:x3hl}{\class{tempstep}{\,\leq u}} \\ \phantom{0}y_4 + \phantom{0}y_5 &= 1 \\ y_4, \;\quad y_5 &\geq 0 \end{align*}
\begin{align*} \phantom{0y_0 + \,}3y_4 + 3y_5 &\leq \data{tempstep-classes=43:red}{\class{tempstep}{1}} \\ 2y_4 + 5y_5 &\leq \data{tempstep-classes=43:red}{\class{tempstep}{1}} \\ 0y_4 + 6y_5 &\leq \data{tempstep-classes=43:red}{\class{tempstep}{1}} \\ \phantom{.} &\phantom{.} \\ y_4, \;\quad y_5 &\geq 0 \end{align*}
Asmpt. 2.11: $P_1, P_2$ are simple   (exactly $m$ or $n$, resp., tight inequalities at each vertex)
Fact 2.13: For simple polytop $P \subseteq \IR^n$ and $\beta: P \to [n], x \mapsto \set{ i \in [n] \sMid i\text{-th inequality tight}}$:
  1. $\forall v,v' \in P \text{ vertices}: v \neq v' \implies \beta(v) \neq \beta(v')$
  2. $\forall v \in P \text{ vertex}, \forall k \in \beta(v): \exists! v' \in P \text{ neighbour of } v: \beta(v') \cap \beta(v) = \beta(v) \setminus \{k\}$
Alg. 2.2: Lemke-Howson
Input: Finite 2-player game $G$ satisfying Assumptions 2.8 and 2.11
Output: A MNE $(x,y)$ of $G$
  1. $x \leftarrow 0, y \leftarrow 0$ and $k \setminus k_0$ for some start label $k_0 \in M$
  2. Repeat:
  3. mm remove label $k$ from $x$; obtain new label $k'$
  4. mm If $k' = k_0$ Then Return $(\mathrm{nrml}(x),\mathrm{nrml}(y))$
  5. mm remove label $k'$ from $y$; obtain new label $k''$
  6. mm If $k'' = k_0$ Then Return $(\mathrm{nrml}(x),\mathrm{nrml}(y))$
  7. mm set $k \leftarrow k''$
Thm. 2.14: The Lemke-Howson algorithm is correct.
Cor. 2.16: Every game satisfying Assumption 2.11 has an odd number of MNE.
\begin{align*} \data{tempstep-classes=4-100:y4hl}{\class{tempstep}{3x_1 + 2x_2 + 3x_3}} &\data{tempstep-classes=4-100:y4hl}{\class{tempstep}{\,\leq 1}} \\ \data{tempstep-classes=4-100:y5hl}{\class{tempstep}{2x_1 + 6x_2 + 1x_3}} &\data{tempstep-classes=4-100:y5hl}{\class{tempstep}{\,\leq 1}} \\ & \\ \data{tempstep-classes=5-100:x1hl}{\class{tempstep}{x_1}}, \;\quad \data{tempstep-classes=5-100:x2hl}{\class{tempstep}{x_2}}, \;\quad \data{tempstep-classes=5-100:x3hl}{\class{tempstep}{x_3}} & \geq 0 \end{align*}
\begin{align*} \data{tempstep-classes=3-100:x1hl}{\class{tempstep}{\phantom{0y_0 + \,}3y_4 + 3y_5}} &\data{tempstep-classes=3-100:x1hl}{\class{tempstep}{\,\leq 1}} \\ \data{tempstep-classes=3-100:x2hl}{\class{tempstep}{2y_4 + 5y_5}} &\data{tempstep-classes=3-100:x2hl}{\class{tempstep}{\,\leq 1}} \\ \data{tempstep-classes=3-100:x3hl}{\class{tempstep}{0y_4 + 6y_5}} &\data{tempstep-classes=3-100:x3hl}{\class{tempstep}{\,\leq 1}} \\ \data{tempstep-classes=5-100:y4hl}{\class{tempstep}{y_4}}, \;\quad \data{tempstep-classes=5-100:y5hl}{\class{tempstep}{y_5}} &\geq 0 \end{align*}
\Huge \data{tempstep-classes=5-100:y4hl}{\class{tempstep}{y_4}} \Huge \data{tempstep-classes=5-100:y4hl}{\class{tempstep}{y_5}} \Huge P_2 \Huge\color{var(--x1color)} \frac{1}{3} \Huge\color{var(--x1color)} \frac{1}{3} \Huge\color{var(--x2color)} \frac{1}{5} \Huge\color{var(--x2color)} \frac{1}{2} \Huge\color{var(--x3color)} \frac{1}{6} \Huge \data{tempstep-classes=5-100:x3hl}{\class{tempstep}{x_3}} \Huge \data{tempstep-classes=5-100:x2hl}{\class{tempstep}{x_2}} \Huge \data{tempstep-classes=5-100:x1hl}{\class{tempstep}{x_1}} \Huge\color{var(--y4color)} \frac{1}{3} \Huge\color{var(--y4color)} \frac{1}{3} \Huge\color{var(--y5color)} \frac{1}{6}
Rem.: There are instances where Lemke Howson requires an exponential number of pivot steps.
Computational Game Theory (WiSe25/26), §2. Computation of Mixed Nash Equilibria
Lukas Graf (lukas.graf@uni-passau.de)
↑ All Slides